#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define ARRAY_SIZE 10

int partion(int arr[],int p,int r){
    int x = arr[r];
    int temp;
    int i=p-1;
    int j=p;
    for(j=p;j<r;j++){
        if(arr[j]<=x){
            i++;
            temp = arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
    temp = arr[i+1];
    arr[i+1]=x;
    arr[r]=temp;
    return i+1;
}

int randomized_partion(int arr[],int p,int r){
    int index = rand()%(r-p)+p;
	int temp = arr[index];
	arr[index]=arr[r];
	arr[r]=temp;
	return partion(arr,p,r);
	
}

void quick_sort(int arr[],int p,int r){
    if(p<r){
        int q = partion(arr,p,r);
        quick_sort(arr,p,q-1);
        quick_sort(arr,q+1,r);
    }
}

int randomized_select1(int arr[],int p,int r,int i){
	if(p==r){
		return arr[p];
	}
	int q = randomized_partion(arr,p,r);
	int k = q-p+1;
	
	if(i==k){
		return arr[q];
	}else if(i<k){
		return randomized_select1(arr,p,q-1,i);
	}else{
		return randomized_select1(arr,q+1,r,i-k);
	}
}

int randomized_select2(int arr[],int p,int r,int i){
	
	while(p<r){
		int q = randomized_partion(arr,p,r);
		int k = q-p+1;
		if(i==k){
			return arr[q];
		}else if(i<k){
			r = q-1;
		}else{
			p = q+1;
			i = i-k;
		}
	}
	return arr[p];
}

int main(){
    int i =1, j = 1;
    int arr[ARRAY_SIZE+1];
	int brr[ARRAY_SIZE+1];
    srand((unsigned)time(NULL));

	int temp = 0;
	while(i<=ARRAY_SIZE){
		temp = rand()%1000;
		for(j=1;j<i;j++){
			if(arr[j]==temp){
				break;
			}
		}
		if(j==i){
			arr[i]=temp;
			i++;
		}
	}
	
	while(i>1){
		brr[i-1]=arr[i-1];
		i--;
	}

    printf("array [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
	
	quick_sort(arr,1,ARRAY_SIZE);
	printf("array [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
	
	i = 5;
    int ret = randomized_select1(brr,1,ARRAY_SIZE,i);
    printf("ret1 %d--%d\n",i,ret);
	
	ret = randomized_select2(arr,1,ARRAY_SIZE,i);
   printf("ret2 %d--%d\n",i,ret);
	
    return 0;
}



